package 动态规划;
//https://www.nowcoder.com/practice/81d7738f954242e5ade5e65ec40e5027?tpId=46&tqId=29106&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
public class 编辑距离 {
    public int minDistance (String word1, String word2) {
        // write code here
        int[][] arr = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0 ; i <= word1.length() ; i ++){
            arr[i][0] = i;
        }
        for (int i = 0 ; i <= word2.length() ; i ++){
            arr[0][i] = i;
        }
        for (int i = 1 ; i <= word1.length() ; i ++){
            for (int j = 1 ; j <= word2.length() ; j ++){
                arr[i][j] = Math.min(arr[i - 1][j] , arr[i][j - 1]) + 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                    arr[i][j] = Math.min(arr[i][j] , arr[i - 1][j - 1]);
                }else {
                    arr[i][j] = Math.min(arr[i][j] , arr[i - 1][j - 1] + 1);
                }
            }
        }
        return arr[word1.length()][word2.length()];
    }
}
